#include <iostream>

using namespace std;

#define N 1000005

int a[N];

struct dequeue{
    int index[N];
    int head;
    int rear;

    bool init(){
        head = rear = 0;
        return true;
    }

    bool empty(){
        if (head == rear){
            return true;
        }
        return false;
    }

    bool push_front(int e){
        for (int i = rear; i > 1; i--){
            index[i + 1] = index[i];
        }
        index[1] = e;
        rear++;
        return true;
    }

    bool push_back(int e){
        index[++rear] = e;
        return true;
    }
        
    bool pop_front(){
        for (int i = 1; i < rear; i++){
            index[i] = index[i + 1];
        }
        rear--;
        return true;
    }

    bool pop_back(){
        rear--;
        return true;
    }

    int front(){
        return index[1];
    }

    int back(){
        return index[rear];
    }
}dq;

int main(){
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++){
        while (!dq.empty() && a[dq.back()] > a[i]){
            dq.pop_back();
        }
        dq.push_back(i);

        if (i >= k){
            while (!dq.empty() && dq.front() <= i - k){
                dq.pop_front();
            }
            cout << a[dq.front()] << " ";
        }
    }

    cout << endl;

    while (!dq.empty()){
        dq.pop_front();
    }
    
    for (int i = 1; i <= n; i++){
        while (!dq.empty() && a[dq.back()] < a[i]){
            dq.pop_back();
        }
        dq.push_back(i);

        if (i >= k){
            while (!dq.empty() && dq.front() <= i - k){
                dq.pop_front();
            }
            cout << a[dq.front()] << " ";
        }
    }

    return 0;
}